package LeetCode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class LC_316_RemoveDuplicateLetters {

    public static void main(String[] args) {

    }

    static class Solution {
        String removeDuplicateLetters(String s) {
            int[] count = new int[26];
            int pos = 0;
            for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) < s.charAt(pos)) pos = i;
                if (--count[s.charAt(i) - 'a'] == 0) break;
            }
            return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
        }

    }

    static class Solution_2 {
        public String removeDuplicateLetters(String s) {
            int[] cnt = new int[200];
            Arrays.fill(cnt, 0);
            int len = s.length();
            char ch;
            for (int i = 0; i < len; i++)
                cnt[s.charAt(i)]++;
            Deque<Character> dq = new ArrayDeque<>();
            for (int i = 0; i < len; i++) {
                ch = s.charAt(i);
                cnt[ch]--;
                if (dq.contains(ch)) continue;
                if (dq.isEmpty() || dq.peekLast() < ch)
                    dq.add(ch);
                else {
                    while (!dq.isEmpty() && dq.peekLast() > ch && cnt[dq.peekLast()] > 0) dq.pollLast();
                    dq.add(ch);
                }
            }
            StringBuilder ans = new StringBuilder();
            while (!dq.isEmpty()) {
                ans.append(dq.peekFirst());
                dq.poll();
            }
            return ans.toString();
        }

    }
}